home *** CD-ROM | disk | FTP | other *** search
/ ADA Programming Guide / ADA Programming Guide.iso / ada_pcdp / ada / ada.doc next >
Encoding:
Text File  |  1996-01-30  |  7.3 KB  |  185 lines
  1.                  Ada Programs 
  2.                     for
  3.  
  4.    Principles of Concurrent and Distributed Programming
  5.                  M. Ben-Ari
  6.          Prentice-Hall International
  7.                    1989
  8.  
  9. 1. Introduction
  10.  
  11. The programs on this diskette are Ada implementations of
  12. concurrent and distributed algorithms. They can be studied
  13. as laboratory exercises or used as a framework for implementing
  14. other algorithms. The programs are written in (standard) Ada
  15. and will run on any (validated) Ada compiler, however,
  16. the implementation of concurrency is not prescribed by
  17. the standard and thus there may be variations in the
  18. behavior of the programs. In any case, the user or
  19. instructor must be familiar with implementation-specific
  20. commands relating to tasking.
  21.  
  22. The behavior of the programs can be followed by inserting
  23. print statements within the tasks. It is possible to influence
  24. the execution of the programs by changing task priorities
  25. or introducting delay statements. A good on-line debugger
  26. is extremely helpful.
  27.  
  28. Some of the programs contain infinite loops while others
  29. have limits on the number of cycles that each task will
  30. execute. Be sure that you know how to interrupt a deadlocked
  31. or non-terminating program.
  32.  
  33. 2. VAX Ada
  34.  
  35. The programs were developed on the VAX Ada compiler under
  36. the VMS operating system. VAX-specific commands used are:
  37.  
  38.   pragma Time_Slice(0.01);
  39.        forces maximum time slicing (10 ms)
  40.  
  41.   pragma Volatile(N);
  42.        forces every access to global variable N to be
  43.        to memory rather than to a register
  44.  
  45. The file VAX.COM contains compilation and link statements
  46. for all the programs. Before compiling Ada programs,
  47. a library must be created using the command ACS CREATE LIBRARY.
  48. After each login (or as part of a batch command file)
  49. the command ACS SET LIBRARY must be given to direct the
  50. compilations and links to the Ada library.
  51.  
  52. 3. Alsys Ada
  53.  
  54. The programs were also run under Alsys Ada. The compiler
  55. ignores the VAX-specific pragmas. Alsys Ada recognizes standard
  56. pragma Shared which should be used instead of Volatile though
  57. the programs worked as is. Tasking is enabled by changing
  58. parameters of the Bind command. The following command should
  59. be used to change default parameters (which can be stored
  60. as part of the initialization file):
  61.  
  62.   DEFAULT.FIND(TIMER=>FAST,SLICE=>10).
  63.  
  64. The file ALSYS.CMD contains compile and bind commands for
  65. all the programs and can be used as a script for the
  66. INVOKE command. A program library must be created and
  67. set before use.
  68.  
  69. 4. List of files
  70.  
  71. The following is a list of the Ada source files on the disk:
  72.  
  73. bakery.ada     -- Lamport's bakery algorithm
  74. buffer.ada     -- Bounded buffer package
  75. defs.ada       -- Linda tuple space definitions
  76. defsbody.ada   -- Package body of defs.ada
  77. dekker.ada     -- Dekker's algorithm
  78. ds.ada         -- Dijkstra-Scholten algorithm
  79. first.ada      -- First attempted solution of mutual exclusion
  80. fourth.ada     -- Fourth attempted solution of mutual exclusion
  81. hard.ada       -- Emulation of hardware primitives
  82. incr.ada       -- Simultaneously increment of a global integer
  83. matrixl.ada    -- Matrix multiplication in Linda
  84. matrixo.ada    -- Matrix multiplication in occam
  85. meex.ada       -- Mutual exclusion using EXCHANGE
  86. mesem.ada      -- Mutual exclusion using semaphore
  87. mets.ada       -- Mutual exclusion using TEST-AND-SET
  88. mon.ada        -- Monitor implementation
  89. pca.ada        -- Producer-consumer in Ada
  90. pcbs.ada       -- Producer-consumer with binary semaphore
  91. pcm.ada        -- Producer-consumer using monitors
  92. pcmon.ada      -- Monitor for producer-consumer
  93. pcs.ada        -- Producer consumer with semaphores
  94. peter.ada      -- Peterson's algorithm
  95. phil1.ada      -- Dining philosophers: first attempt
  96. phila.ada      -- Dining philosophers: asymmetric solution
  97. philm.ada      -- Dining philosophers: monitor solution
  98. philr.ada      -- Dining philosophers: Room semaphore
  99. phmon.ada      -- Monitor for dining philosophers
  100. ra.ada         -- Ricart-Agrawala algorithm
  101. rw.ada         -- Readers and writers
  102. rwmon.ada      -- Monitor for readers and writers
  103. second.ada     -- Second attempted solution of mutual exclusion
  104. sem.ada        -- Semaphore package
  105. snap.ada       -- Snapshot algorithm
  106. tasksl.ada     -- Tasks for Linda tuple space
  107. taskso.ada     -- Tasks for occam matrix multiplication
  108. third.ada      -- Third attempted solution of mutual exclusion
  109. tm.ada         -- Terminate-with-marking algorithm
  110. tup.ada        -- Emulation of Linda tuple space
  111. tupbody.ada    -- Package body for tup.ada
  112. workers.ada    -- Worker tasks for Linda matrix multiplication
  113.  
  114. 5. Comments on the programs
  115.  
  116. 5.1 Mutual exclusion algorithms
  117.  
  118. The common memory algorithms depend on time slicing. However,
  119. given the long duration of the 10 ms. slice relative to the
  120. speed of execution of the algorithms, it is difficult, if not
  121. impossible to actually see some of the pathologies.
  122. INCR clearly shows the unpredictability of concurrency and
  123. THIRD does deadlock.
  124.  
  125. Package HARD simulates hardware primitives EXCHANGE and
  126. TEST-AND-SET.
  127.  
  128. 5.2 Semaphores
  129.  
  130. Semaphores are implemented using (private) task types.
  131. There are separate types for (general) semaphores and
  132. binary semaphores. Binary semaphores ignore Signal instructions
  133. if the value is 1. All semaphores must be explicitly initialized.
  134.  
  135. 5.3 Producer-Consumer solutions
  136.  
  137. Producers are given a higher priority than consumers to allow
  138. the buffer to fill up. Occasionally, proceducers are delayed
  139. so that the buffer can be emptied.
  140.  
  141. 5.4 Monitors
  142.  
  143. The design of the monitor implementation is discussed in the book.
  144. Note that the implementation assumes that every Signal is the
  145. last statement in its procedure.
  146.  
  147. 5.5 Dining philosophers
  148.  
  149. PHIL1 is supposed to deadlock. PHMON contains two Signals
  150. in a monitor procedure. This causes the program to deadlock
  151. when the finite number of Think-Eat cycles have been completed.
  152.  
  153. 5.6 occam
  154.  
  155. As discussed in the book, the emulation of occam is not very
  156. transparent because of the mismatch between the symmetric
  157. channel addressing in occam as opposed to the asymmetric task
  158. addressing in Ada. The solution chosen should allow an instructor
  159. familiar with Ada to construct a skeleton for other occam programs
  160. by rewriting Task_Types, Tasks and Channel_Task. Activation and
  161. configuration should also be supplied to the student who could
  162. then write the individual task bodies and experiment with them.
  163.  
  164. 5.7 Linda
  165.  
  166. The tuple package contains tasks that synchronize access to the
  167. tuple space. Termination of tasks that depend on a library
  168. package is not defined in the standard. The VAX implementation
  169. does terminate the program, but problems have been observed
  170. in the Alsys implementation. The solution would be to 
  171. insert the package into the main program MATRIXL so that
  172. the tasks would depend on the main procedure rather than
  173. a library package.
  174.  
  175. 5.8 Distributed algorithms
  176.  
  177. Even though these algorithms use global variables to communicate
  178. between the various tasks comprising one "node", time slicing
  179. is not required because delay statements have been inserted
  180. to force the scheduler to run as needed.
  181.  
  182. The Dijkstra-Scholten algorithm does not terminate. After
  183. the source node announces that the system has terminated, the
  184. tasks that look for messages will still run indefinitely and
  185. the program must be manually interrupted.